"""
1824. 最少侧跳次数
中等
相关标签
相关企业
提示
给你一个长度为 n 的 3 跑道道路 ，它总共包含 n + 1 个 点 ，编号为 0 到 n 。一只青蛙从 0 号点第二条跑道 出发 ，它想要跳到点 n 处。然而道路上可能有一些障碍。

给你一个长度为 n + 1 的数组 obstacles ，其中 obstacles[i] （取值范围从 0 到 3）表示在点 i 处的 obstacles[i] 跑道上有一个障碍。如果 obstacles[i] == 0 ，那么点 i 处没有障碍。任何一个点的三条跑道中 最多有一个 障碍。

比方说，如果 obstacles[2] == 1 ，那么说明在点 2 处跑道 1 有障碍。
这只青蛙从点 i 跳到点 i + 1 且跑道不变的前提是点 i + 1 的同一跑道上没有障碍。为了躲避障碍，这只青蛙也可以在 同一个 点处 侧跳 到 另外一条 跑道（这两条跑道可以不相邻），但前提是跳过去的跑道该点处没有障碍。

比方说，这只青蛙可以从点 3 处的跑道 3 跳到点 3 处的跑道 1 。
这只青蛙从点 0 处跑道 2 出发，并想到达点 n 处的 任一跑道 ，请你返回 最少侧跳次数 。

注意：点 0 处和点 n 处的任一跑道都不会有障碍。

 

示例 1：


输入：obstacles = [0,1,2,3,0]
输出：2 
解释：最优方案如上图箭头所示。总共有 2 次侧跳（红色箭头）。
注意，这只青蛙只有当侧跳时才可以跳过障碍（如上图点 2 处所示）。
示例 2：


输入：obstacles = [0,1,1,3,3,0]
输出：0
解释：跑道 2 没有任何障碍，所以不需要任何侧跳。
示例 3：


输入：obstacles = [0,2,1,0,3,0]
输出：2
解释：最优方案如上图所示。总共有 2 次侧跳。
 

提示：

obstacles.length == n + 1
1 <= n <= 5 * 105
0 <= obstacles[i] <= 3
obstacles[0] == obstacles[n] == 0
"""


class Solution(object):
    """
    整体思路：从左往右遍历二维数组，每一列要么从左边跳过来，要么左边由石头则需从上下调过来；
    但是注意左边有石头上下跳动的情况，是需要从左边跳过后再往上下跳动，所以应先计算从左往右没石头的情况，从没石头的情况中，再计算从哪跳到有石头位置更好
    """
    def minSideJumps(self, obstacles):
        m = 3
        n = len(obstacles)
        dp = [[float('inf')] * n for _ in range(m)]
        dp[1][0] = 0
        dp[0][0] = 1 #初始位置可以上下移动，记为次数1
        dp[2][0] = 1
        for j in range(1,n):
            for i in range(m):
                if obstacles[j] -1 != i:
                    dp[i][j] = dp[i][j-1]
            for i in range(m):
                if obstacles[j] -1 == i:
                    continue
                #查看是否能从其他位置跳转到当前，obstacles[j] -1时因为0代表没有，3代表第三条跑道，但是这里i使用的的是索引[0,2]，跑到3索引应该是2
                if obstacles[j] -1 != (i+1)%m:
                    dp[i][j] = min(dp[i][j], dp[(i + 1) % m][j - 1] + 1)
                if obstacles[j] - 1 != (i + 2) % m:
                    dp[i][j] = min(dp[i][j], dp[(i + 2) % m][j - 1] + 1)
        #结果
        return min(dp[i][-1] for i in range(m))
    def minSideJumps_err1(self, obstacles):
        """
        :type obstacles: List[int]
        :rtype: int
        """
        m = len(obstacles)
        n = 3
        #创建dp
        dp = [[float('inf')] * m for _ in range(n)]
        dp[1][0] = 0
        for j in range(1, m):
            for i in range(n):
                #同一行的
                if obstacles[j] == i+1:
                    continue
                dp[i][j] = min(dp[i][j], dp[i][j-1])
                #其他行的
                i1 = (i+1)%3
                dp[i][j] = min(dp[i][j], dp[i1][j-1] + 1)
                i2 = (i+2)%3
                dp[i][j] = min(dp[i][j], dp[i2][j-1] + 1 )
        res = float('inf')
        for i in range(n):
            if obstacles[m-1] - 1 != i:
                res = min(res, dp[m-1][i])
        return res

if __name__ == '__main__':
    # print(Solution().minSideJumps([0,1,2,3,0]))
    # print(Solution().minSideJumps([0,1,1,3,3,0]))
    print(Solution().minSideJumps([0,2,1,0,3,0]))